package 双指针

/*
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
*/
func trap(height []int) int {

	if len(height) <= 2 { //数组长度如果小于等于2, 那么不能接住雨水, 直接返回即可
		return 0
	}

	//声明切片, 初始容量为1, 容量为height数组长度
	st := make([]int, len(height)) // 切片模拟单调栈，st存储的是高度数组下标
	st = append(st, 0)             //将0柱子放入栈

	var res int //声明结果变量

	for i := 1; i <= len(height)-1; i++ { //0下标柱子已经放入栈了, 从1遍历即可
		if height[i] < height[st[len(st)-1]] { //如果当前元素 < 栈口元素, 没有打破栈的单调递增性, 直接加入栈
			st = append(st, i)
		} else if height[i] == height[st[len(st)-1]] { //如果与栈口元素相等, 将栈口元素弹出, 将当前元素下标加入栈中
			st = st[:len(st)-1] // 比较的新元素和栈顶的元素相等，去掉栈中的，入栈新元素下标
			st = append(st, i)
		} else { //否则当前元素 > 栈口元素了, 满足了形成雨水的凹槽, 累加计算雨水体积
			for len(st) != 0 && height[i] > height[st[len(st)-1]] { //只要栈不为空 && 当前元素>栈口元素
				mid := st[len(st)-1] //获取栈顶元素(中柱子)
				st = st[:len(st)-1]  //弹出栈顶元素
				if len(st) != 0 {
					//计算当前三个柱子形成的雨水面积, 与结果计数累加
					//			 右柱子				左柱子
					temp := (min(height[i], height[st[len(st)-1]]) - height[mid]) * (i - st[len(st)-1] - 1)
					res += temp //雨水体积累加
				}
			}

			//计算完毕后, 将当前柱子下标, 加入栈中
			st = append(st, i)
		}
	}
	return res
}
